package sortAlgorithm.shellSort;

import java.util.Arrays;

/**
 * @author： pang-yun
 * @date： 2021-09-23 20:29
 * 功能目的 ：用于  希尔排序  移动法
 * 交换法 效率太低  每次都要交换
 */
// 插入法 进阶版
public class ShellSortMove {
    public static void main(String[] args) {
        int[] arr = new int[]{11, 10, 9, 0, 7, 8, 6, 5};
        shellSortMove(arr);
    }

    public static void shellSortMove(int[] arr) {
        int insertIndex = 0;   // 插入索引
        int insertVal = 0;    //  要插入的值
        for (int step = arr.length / 2; step > 0; step /= 2) {   // 步长
            for (int i = step; i < arr.length; i++) {     // 下面为 insertSort
                insertVal = arr[i];    // 获取 插入值
                insertIndex = i - step;  // 与插入值同一组 的 前一个值的索引
                while (insertIndex >= 0 && insertVal < arr[insertIndex]) {  // 前一个值的  索引大于0  并且  插入值 要小于前一个值  那么前一个值后移，
                    // 再对 前一个值 的 前一个值 进行比较   直到插入值大于它  那么就找到了 插入值的  要插入的正确位置
                    arr[insertIndex + step] = arr[insertIndex];
                    insertIndex -= step;
                }
                arr[insertIndex + step] = insertVal;   // 将插入值放入 正确位置 再进行下一次 插入
            }
            System.out.println(Arrays.toString(arr));
        }
    }





   /* public static void shellSortMove(int[] arr) {
        // 增量gap 并逐步缩小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 从 第gap 个元素开始 逐个对其所在的组进行插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[i];
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        //移动
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    // 当退出while后 就给 temp 找到了插入的位置
                    arr[j] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
    }*/
}
